public class test {
    //leetcode 53.最大子数组和
    class Solution {
        // 解法1. 滑动窗口 + 前缀和
        public int maxSubArray1(int[] nums) {
            // 前缀和
            int sum = nums[0];
            // 最大值
            int max = nums[0];
            int left = 0;
            int right = 0;
            while (right < nums.length - 1) {
                right++;
                sum += nums[right];
                // 如果nums[right] > sum,则代表sum中有人拖后腿
                while (nums[right] > sum) {
                    sum -= nums[left];
                    left++;
                }
                // 记录最大值
                max = Math.max(max, sum);
            }
            return max;
        }

        // 解法2. 动态规划
        public int maxSubArray(int[] nums) {
            // 1. 创建dp[]表
            // dp[i] 代表[0,i]范围内的最大子数组
            int n = nums.length;
            int[] dp = new int[n];
            // 2. 初始化
            dp[0] = nums[0];
            // 3. 填表
            int max = nums[0];
            for (int i = 1; i < n; i++) {
                dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
                max = Math.max(max, dp[i]);
            }
            // 4. 返回值
            return max;
        }
    }
    //leetcode 918.环形子数组的最大和
    class Solution {
        public int maxSubarraySumCircular(int[] nums) {
            // 1. 创建dp[]表
            int n = nums.length;
            if(n == 1){
                return nums[0];
            }
            int[] dpmax = new int[n];
            int[] dpmin = new int[n];
            // 2. 初始化
            //记录数组的前缀和
            int sum = nums[0];
            //记录数组的最大值和最小值
            int max = nums[0];
            int min = nums[0];
            dpmax[0] = nums[0];
            // 3. 填表
            for(int i = 1;i < n;i++){
                dpmax[i] = Math.max(dpmax[i-1] + nums[i],nums[i]);
                dpmin[i] = Math.min(dpmin[i-1] + nums[i],nums[i]);
                max = Math.max(max,dpmax[i]);
                min = Math.min(min,dpmin[i]);
                sum += nums[i];
            }
            // 4. 返回值
            return Math.max(max,sum - min);
        }
    }
    //leetcode 152.乘积最大子数组
    class Solution {
        public int maxProduct(int[] nums) {
            // 1. 创建dp[]表
            int n = nums.length;
            // dp1用于检查乘积最大子数组,用于与正数相乘
            long[] dp1 = new long[n];
            // dp2用于检查乘积最小子数组,用于与负数相乘
            long[] dp2 = new long[n];
            // 2. 初始化
            dp1[0] = nums[0];
            dp2[0] = nums[0];
            long max = nums[0];
            // 3. 填表
            for (int i = 1; i < n; i++) {
                int num = nums[i];
                long big = 0;
                long small = 0;
                //当 num > 0 时
                // 取[i-1]处的最'大'子数组相乘(才能变大)
                // 取[i-1]处的最'小'子数组相乘(才能变小)
                //当 num < 0 时
                // 取[i-1]处的最'小'子数组相乘(才能变大)
                // 取[i-1]处的最'大'子数组相乘(才能变小)
                if(num > 0){
                    big = dp1[i - 1] * num;
                    small = dp2[i - 1] * num;
                }else if(num < 0){
                    big = dp2[i - 1] * num;
                    small = dp1[i - 1] * num;
                }
                dp1[i] = Math.max(num,big);
                dp2[i] = Math.min(num,small);
                max = Math.max(dp1[i], max);
            }
            // 4. 返回值
            return (int) max;
        }
    }
}
